Minimum Size Subarray Sum

Algorithm>LeetCode

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

题目大意： 给定一个正数数组 nums和一个正数 s，找出最短长度的连续子数组 使其和 大于等于 s。如果没有的话，返回 0.

Solution

暴力枚举 Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        size_t n = nums.size();
        int sum = 0;
        int ans = INT_MAX;
        for(int i=0;i<n;i++){
            sum = nums[i];
            if(sum >= s) return 1;
            for(int j=i+1;j<n;j++){
                sum += nums[j];
                if(sum >= s){
                    ans = min(ans,j-i+1);
                    break;
                }
            }
        }
        
        return ans==INT_MAX ? 0 : ans;
    }
};

暴力枚举 + flag优化 Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        size_t n = nums.size();
        int sum = 0;
        int ans = INT_MAX;
        
        bool flag;
        for(int i=0;i<n;i++){
            sum = nums[i];
            if(sum >= s) return 1;
            flag = false;
            for(int j=i+1;j<n;j++){
                sum += nums[j];
                if(sum >= s){
                    ans = min(ans,j-i+1);
                    flag = true;
                    break;
                }
            }
            
            if(!flag) break;
        }
        
        return ans==INT_MAX ? 0 : ans;
    }
};

枚举小窗口 Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        size_t n = nums.size();
        int sum = 0;
        int ans = INT_MAX;
        int p = 0,q = 0;
        
        while(q < n){
            sum += nums[q++];
            
            while(sum >= s){
                ans = min(ans,q-p);
                sum -= nums[p++];
            }
            
        }
        
        return ans==INT_MAX ? 0 : ans;
    }
};